package com.lfg.leetcode.leetcode0;

import java.util.ArrayList;
import java.util.List;

public class No95generateTrees {

    public static void main(String[] args) {
        List<TreeNode> ret = generateTrees(3);
        for (TreeNode str : ret) {
            System.out.println("[" + str.val + "]");
        }
    }

    public static List<TreeNode> generateTrees(int n) {
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = i + 1;
        }
        return getTreeNode(nums, 0, n - 1);
    }

    public static List<TreeNode> getTreeNode(int[] nums, int start, int end) {
        List<TreeNode> ret = new ArrayList<>(nums.length * 2);
        if (start > end) {
            return ret;
        }
        if (start == end) {
            ret.add(new TreeNode(nums[start]));
            return ret;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> left = getTreeNode(nums, start, i - 1);
            List<TreeNode> right = getTreeNode(nums, i + 1, end);
            if (left.size() == 0) {
                for (TreeNode treeNode : right) {
                    TreeNode root = new TreeNode(nums[i]);
                    root.right = treeNode;
                    ret.add(root);
                }
            }
            if (right.size() == 0) {
                for (TreeNode treeNode : left) {
                    TreeNode root = new TreeNode(nums[i]);
                    root.left = treeNode;
                    ret.add(root);
                }
            }
            for (TreeNode leftNode : left) {
                for (TreeNode rightNode : right) {
                    TreeNode root = new TreeNode(nums[i]);
                    root.right = rightNode;
                    root.left = leftNode;
                    ret.add(root);
                }
            }
        }
        return ret;
    }
}

